#include <stdio.h>

/**
 * @brief 快速排序
 * @param left 指向当前要排序的部分的最左边
 * @param right 指向当前要排序的部分的最右边
 * @return 无
 */
void quickSort(int *arr, int left, int right){
    // 越界判断
    if(left>right){
        return;
    }
    // 1.设置中轴(先临时取当前最左边的位置，作为中轴)
    int pivot = arr[left];
    // 2.设置辅助"指针"变量来进行遍历操作
    int i=left,j=right;
    int temp=0;
    // 3.开始查找，只要还没相遇，就一直要继续
    while(i!=j){
        // j控制从右往左找，查找第一个比pivot小的元素
        // j>i 防止越界
        // 直到找到了指定元素，停下；
        // 或者没有找到，扫到了最左边，也停下来
        while (arr[j]>=pivot && j>i){
            j--;
        }
        // i控制从左往右找，查找第一个比pivot大的元素
        while(arr[i]<=pivot&&i<j){
            i++;
        }
        // 当都停下后，互换i和j位置的元素
        temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;        
    }
    // 4.设置pivot中轴正确的位置
    arr[left] = arr[i];
    arr[i]=pivot;
    // 5.中轴归位后，中轴左边的元素，都是比它小的元素
    // 中轴右边的元素，都是比它大的元素
    // 再分别整理中轴左边的元素列表
    quickSort(arr,left,i-1);
    // 再分别整理中轴右边的元素列表
    quickSort(arr,i+1,right);
}

int main(void){
    int nums[] = {10, 51, 89, 90, 23, 5, 100};
    int size = sizeof(nums)/sizeof(nums[0]);
    quickSort(nums,0,size-1);
    for (int i = 0; i < size; i++){
        printf("%d ",nums[i]);
    }
    printf("\n");
    
    return 0;
}
